// 3SumClosest.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

//3Sum Closest

//Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. 
//Return the sum of the three integers. You may assume that each input would have exactly one solution.

#include <vector>
#include <algorithm>
using namespace std;
int ThreeSumClosest(vector<int>& num, int target)
{
	if(num.size() < 3) return INT_MIN;
	sort(num.begin(), num.end());
	int nSum = num[0]+num[1]+num.back();
	if(num.size() == 3) return nSum;
	
	for(int i = 0; i< (int)num.size() -2; i++)
	{
		int k = num.size() -1;
		int j = i+1;
		while(j<k)
		{
			int nTemp = num[i]+num[j]+num[k];
			if(nTemp == target) return nTemp;
			if(abs(target - nTemp) < abs(target - nSum)) 
			{
				nSum = nTemp;
			}
			
			if(nSum < target)
				j++;
			else
				k--;
		}

	}

	return nSum;
}

int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}

